// geometry.cc

#include <cassert>
#include <vector>
#include "geometry.h"

using namespace std;

// The first goal in this file is to establish a special coordinate
// system such that every node, edge, and tile in a hexagonal grid is
// represented by a distinct (x, y) coordinate pair.  To that end,
// here is a bad picture of a single hexagonal tile:
//
//     .-.
//     - -
//     .*.
//     _ _
//     .-.
//
// Here, the * represents the center of the hexagon.  This is
// surrounded by a ring of six edges denoted by dashes alternating
// with six nodes denoted by dots.  So the picture is crude, but shows
// all the geometric elements of a hexagon in roughly the right places.
//
// Suppose we take the lower-left dot in this hexagon as an origin.
// Then this dot has coordinates (0, 0).  The edge just above has
// coordinates (0, 1).  The center of the hexagon is at (1, 2), and
// the opposite node is at (2, 4).  So now we have a coordinate system
// to describe the components of a single hexagon.
//
// Let's extend the bad picture by adding an adjacent hexagonal tile
// above and to the right of the original:
//
//       .-.
//       - -
//     .-.*. <--- This is the new hexagon.
//     - - -
//     .*.-.
//     _ _
//     .-.
//
// Note that the two tiles share a single edge and two nodes, as they
// should in a hexagon grid.  We can extend the coordinate system to
// describe components of this next hexagon as well.  For example, the
// shared edge is at (2, 3), and the new tile is centered at (3, 4).
//
// We can continue in this way, extending this bad picture of two
// hexagons into a bad picture of an infinite hexagon grid:
//
//     | | | | | |
//     .*.-.*.-.*.-
//     | | | | | |
//     .-.*.-.*.-.*
//     | | | | | |
//     .*.-.*.-.*.-
//     | | | | | |
//     .-.*.-.*.-.*
//     | | | | | |
//     .*.-.*.-.*.-
//     | | | | | |
//     .-.*.-.*.-.*
//
// And we can refer to any node, edge, or hexagonal tile in this grid
// with a unique pair of coordinates.
//
// Notice that the picture shown above is like a repeating wallpaper
// pattern.  Each symbol is the same as the one four steps to the
// right, and each symbol is the same at the one four steps up.
// Therefore, the symbol at position (x, y) is the same as the symbol
// at position (x mod 4, y mod 4).  So, from a 4x4 pattern, once can
// reconstruct the entire hexagonal grid.  That's done below.

static const char *pattern[4] = {
  ".-.*",
  "- - ",
  ".*.-",
  "- - ",
};

bool Geometry::IsTile(int x, int y) {
  return pattern[y & 3][x & 3] == '*';
}

bool Geometry::IsEdge(int x, int y) {
  return pattern[y & 3][x & 3] == '-';
}

bool Geometry::IsNode(int x, int y) {
  return pattern[y & 3][x & 3] == '.';
}

// The second goal in this file is shed light on adjacency
// relationships.  Given the (x, y) coordinates of an object, one
// ought to be able to get the (x, y) coordinate of all adjacent
// objects of a given type.  For example, 



// Two objects in Hexworld are adjacent if they are joined by one of
// the following symbol sequences.  For example, the rule that two
// nodes are adjacent if they are joined by an edge is represented by
// the ".-." string.  Similarly, two hexagonal tiles are adjacent if
// there is a path between them consisting of a blank space, a edge,
// and another blank space; thus, the string "* - *".

static const char *path[] = {
  "-.", ".-", "*.", ".*", ".-.", "-.-",
  "* -", "- *", "* -.", ".- *", "* - *", NULL
};

// The pattern array and path strings together define the positions of
// all geometric entities and their adjacency relationship.  For
// speed, adjacency information is precomputed and stored in the
// following structure:

static struct Adj {
  vector<pair<int, int> > tiles;
  vector<pair<int, int> > edges;
  vector<pair<int, int> > nodes;
} adjacent[4][4];

// Nodes adjacent to the entity at position (x, y) are described in
// the adjacent[x & 3][y & 3].nodes vector.  (Adjacent tiles and edges
// are stored similarly.)  More precisely, the vector stores the
// _relative_ positions of the adjacent nodes.  So, for example, if
// (x, y) is the position of a tile, then the corresponding nodes
// vector would contain these six pairs:
//
//   (-1,  2)    ( 1,  2)
//   (-1,  0)    ( 1,  0)
//   (-1, -2)    ( 1, -2)
//
// This reflects arragement of nodes around each tile:
//
//     .-.
//     | |
//     .*.
//     | |
//     .-.

int Geometry::NumAdjTiles(int x, int y) {
  return adjacent[x & 3][y & 3].tiles.size();
}

int Geometry::NumAdjEdges(int x, int y) {
  return adjacent[x & 3][y & 3].edges.size();
}

int Geometry::NumAdjNodes(int x, int y) {
  return adjacent[x & 3][y & 3].nodes.size();
}

void Geometry:: AdjTile(int x, int y, int i, int *tx, int *ty) {
  pair<int, int> &obj = adjacent[x & 3][y & 3].tiles[i];
  *tx = x + obj.first;
  *ty = y + obj.second;
}

void Geometry:: AdjEdge(int x, int y, int i, int *ex, int *ey) {
  pair<int, int> &obj = adjacent[x & 3][y & 3].edges[i];
  *ex = x + obj.first;
  *ey = y + obj.second;
}

void Geometry:: AdjNode(int x, int y, int i, int *nx, int *ny) {
  pair<int, int> &obj = adjacent[x & 3][y & 3].nodes[i];
  *nx = x + obj.first;
  *ny = y + obj.second;
}

// The Init() function fills in the adjacency structure based on the
// 'pattern' array and 'path' list.  In particular, the search()
// function is called for each point (x, y) in the pattern and each
// path-string.  The function recursively finds all distinct objects
// that can be reached from point (x, y) by traversing precisely the
// sequence of symbols in the path string.  The results are stored in
// the adjacency structure.
static void search(int x, int y, int dx, int dy, const char *path, Adj *adj) {
  // The search route must be consistent with the path string.
  if (*path != pattern[(y + dy) & 3][(x + dx) & 3])
    return;

  // If the path string is not exhausted, try to extend the search
  // route in every possible direction.
  if (*(path + 1)) {
    search(x, y, dx - 1, dy, path + 1, adj);
    search(x, y, dx + 1, dy, path + 1, adj);
    search(x, y, dx, dy - 1, path + 1, adj);
    search(x, y, dx, dy + 1, path + 1, adj);
    return;
  }

  // We've found a route to an adjacent object.  But an object can not
  // be adjacent to itself.
  if (dx == 0 && dy == 0)
    return;

  // Get the vector to which the adjacent object belongs.
  vector<pair<int, int> > *adj_list =
    *path == '*' ? &adj->tiles :
    *path == '-' ? &adj->edges :
    *path == '.' ? &adj->nodes : NULL;

  // Consider each adjacent object only once, even if it can be
  // reached by multiple routes.
  pair<int, int> offset = make_pair(dx, dy);
  for(int i = 0; i < adj_list->size(); i++)
    if ((*adj_list)[i] == offset)
      return;

  // Add the neighboring object to the adjacency structure.
  adj_list->push_back(offset);
}

void Geometry::GetOriginTile(int *tx, int *ty) {
  // There must be at least one tile within the 3x3 pattern array.
  // Return the one with smallest sum of coordinates.
  for (int r = 0; r <= 6; r++) {
    for (int x = 0; x <= r; x++) {
      int y = r - x;
      if (IsTile(x, y)) {
	*tx = x;
	*ty = y;
	return;
      }
    }
  }
  assert(false);
}

void Geometry::Init() {
  for (int y = 0; y < 4; y++)
    for (int x = 0; x < 4; x++)
      for(int i = 0; path[i]; i++)
	search(x, y, 0, 0, path[i], &adjacent[x][y]);
}
